from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 找出s中所有的p的异位词的开始 (这道题是个定长的字符串)
        left, right = 0, 0
        valid = 0
        window = {}
        need = {}
        res = []
        for i in p:
            need[i] = need.get(i, 0) + 1
        while right < len(s):
            a = s[right]
            right += 1
            if a in need:
                window[a] = window.get(a, 0) + 1
                if window[a] == need[a]:
                    valid += 1
            if right - left >= len(p):
                if valid == len(need):
                    res.append(left)
                b = s[left]
                left += 1
                if b in need:
                    if window[b] == need[b]:
                        valid -= 1
                    window[b] = window.get(b, 0) - 1

        return res
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    # your test code here